#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    public:
    //深度优先
    int ans1(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        deep = max(ans1(root->left), ans1(root->right)) + 1;
        return deep;
    }

    //广度优先
    int ans2(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        queue<TreeNode*> Q;
        Q.push(root);
        int ans = 0;
        while(!Q.empty()){
            int len = Q.size();
            while(len > 0){
                TreeNode* node = Q.front();
                Q.pop();
                if(node->left){
                    Q.push(node->left);
                }
                if(node->right){
                    Q.push(node->right);
                }
                len--;
            }
            ans++;
        }
        return ans;
    }

    TreeNode* createTree(vector<int> nums, int index, int len){
        if(nums[index] == '#'){
            return NULL;
        }
        TreeNode* root = new TreeNode(nums[index]);

        if(index * 2 + 1 < len){
            root->left = createTree(nums, index * 2 + 1, len);
        }else{
            root->left = NULL;
        }
        if(index * 2 + 2 < len){
            root->right = createTree(nums, index * 2 + 2, len);
        }else{
            root->right = NULL;
        }
        return root;
    }

    void frontTraverse(TreeNode* root){
        if(root == nullptr){
            return;
        }
        val.push_back(root->val);
        frontTraverse(root->left);
        frontTraverse(root->right);
    }

    void show(){
        int len = val.size();
        for(int i = 0; i != len-1; i++){
            cout << val[i] << " " << ends;
        }
        cout << val[len-1] << endl;
    }

    private:
    vector<int> val;
    int deep;
};

void test1(){
    Solution s;

    vector<int> num = {3,9,20,'#','#',15,7};
    int len = num.size();
    TreeNode* root = s.createTree(num, 0, len);
    // s.frontTraverse(root);
    // s.show();
    int ret = s.ans1(root);
    cout << ret << endl;
    
}



int main(void){
    test1();

    return 0;
}